package datastructure.graph.无向图;

import java.util.Stack;

/**
 * @author MaoLin Wang
 * @description
 * @date 2020/8/27 2:24 下午
 */
public class DepthFirstSearch {
    private boolean[] marked;

    private int[] edgeTo;

    private int s;

    public DepthFirstSearch(Graph graph, int s) {
        this.s = s;
        marked = new boolean[graph.getV()];
        edgeTo = new int[graph.getV()];
        dfs(graph, s);
    }

    private void dfs(Graph graph, int s) {
        marked[s] = true;
        for (Integer w : graph.adj(s)) {
            if (!marked[w]) {
                edgeTo[w] = s;
                dfs(graph, w);
            }
        }
    }

    public boolean hasPathTo(int v) {
        return marked[v];
    }

    public Stack<Integer> pathTo(int v) {
        if (!hasPathTo(v)) {
            return null;
        }
        Stack stack = new Stack();
        for (int i = v; i != s; i = edgeTo[i]) {
            stack.push(i);
        }
        stack.push(s);
        return stack;

    }

    public static void main(String[] args) {
        Graph graph = new Graph(6);
        graph.addEdge(0, 2);
        graph.addEdge(0, 1);
        graph.addEdge(0, 5);
        graph.addEdge(2, 1);
        graph.addEdge(2, 3);
        graph.addEdge(2, 4);
        graph.addEdge(3, 5);
        graph.addEdge(3, 4);
        DepthFirstSearch dfs = new DepthFirstSearch(graph, 0);
        System.out.println(dfs.hasPathTo(4));
        Iterable<Integer> paths = dfs.pathTo(4);
        System.out.println(paths);
        int[] edgeTo = dfs.edgeTo;

    }
}
